//
// Created by liushuai on 2021/2/27.
//

#include "findOrder.h"

void dfs(int u, vector<int> &visited_status, vector<vector<int>> &connect, vector<int> &result, bool &valid) {
    visited_status[u] = 1;
    for (int next_node:connect[u]) {
        if (visited_status[next_node] == 0) {
            dfs(next_node, visited_status, connect, result, valid);
            if (!valid)
                return;
        } else if (visited_status[next_node] == 1) {
            valid = false;
            return;
        }
    }
    visited_status[u] = 2;
    result.push_back(u);

}

vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites) {
    vector<int> visited_status(numCourses, 0);
    vector<int> result;
    vector<vector<int>> connect(numCourses, vector<int>());
    bool valid = true;
    for (auto edge:prerequisites) {
        connect[edge[1]].push_back(edge[0]);
    }
    for (int i = 0; i < numCourses && valid; i++) {
        if (!visited_status[i])
            dfs(i, visited_status, connect, result, valid);
    }
    if (!valid)
        return {};
    std::reverse(result.begin(), result.end());
    return result;
}

void findOrder1(int numCourses, vector<vector<int>> &prerequisites, vector<int> &inNode, vector<vector<int>> &connect,
                vector<int> &result, queue<int> visited_queue) {
    for (auto node:prerequisites) {
        inNode[node[0]] += 1;
        connect[node[1]].push_back(node[0]);
    }

    for (int i = 0; i < inNode.size(); i++) {
        if (inNode[i] == 0) {
            visited_queue.push(i);
        }
    }
    while (!visited_queue.empty()) {
        int node = visited_queue.front();
        result.push_back(node);
        visited_queue.pop();
        for (auto connected_node:connect[node]) {
            inNode[connected_node] -= 1;
            if (inNode[connected_node] == 0)
                visited_queue.push(connected_node);
        }
    }
    if (result.size() != numCourses)
        result = {};

}

vector<int> findOrder1(int numCourses, vector<vector<int>> &prerequisites) {
    vector<int> inNode(numCourses, 0);
    vector<vector<int>> connect(numCourses, vector<int>());
    vector<int> result;
    queue<int> visited_queue;
    findOrder1(numCourses, prerequisites, inNode, connect, result, visited_queue);
    return result;
}